class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int> > rst(n, vector<int>(n, -1));

        int row = 0;
        int col = -1;
        int i = 0;

        while(i < n * n) {
            // move left
            while(col + 1 < n && rst[row][col + 1] == -1){
                rst[row][++col] = ++i;
            }
            // move down
            while(row + 1 < n && rst[row + 1][col] == -1){
                rst[++row][col] = ++i;
            }
            // move right
            while(col - 1 >= 0 && rst[row][col - 1] == -1){
                rst[row][--col] = ++i;
            }
            // move up
            while(row - 1 >= 0 && rst[row - 1][col] == -1){
                rst[--row][col] = ++i;
            }
        }

        return rst;
    }
};